package arrAndstr;

import java.util.Arrays;

/*
	106. 从中序与后序遍历序列构造二叉树
 */
public class T106 {


	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}


	public static void main(String[] args) {
		int[] inorder = {9, 3, 15, 20, 7}, postorder = {9, 15, 7, 20, 3};

		TreeNode root = buildTree(inorder, postorder);

	}

	// inorder:   左子树 根 右子树
	// postorder: 左子树 右子树 根
	public static TreeNode buildTree(int[] inorder, int[] postorder) {
		int inorderLen = inorder.length;
		int postorderLen = postorder.length;
		int value = postorder[postorderLen - 1];

		TreeNode root = new TreeNode(value);
		int valueIndex = getValueIndex(inorder, value);
		if (valueIndex - 0 > 0) {
			root.left = buildTree(Arrays.copyOfRange(inorder, 0, valueIndex), Arrays.copyOfRange(postorder, 0, valueIndex));
		}
		if (inorderLen - valueIndex - 1 > 0) {
			root.right = buildTree(Arrays.copyOfRange(inorder, valueIndex + 1, inorderLen), Arrays.copyOfRange(postorder, valueIndex, postorderLen - 1));
		}

		return root;
	}

	private static int getValueIndex(int[] inorder, int value) {
		for (int i = 0; i < inorder.length; i++) {
			if (inorder[i] == value) return i;
		}
		return -1;
	}
}
